Tháng 10 năm 2004, Tony Blair tuyên bố rút lui khỏi vị trí lãnh đạo đảng trong cuộc tổng tuyển cử lần thứ tư, nhưng sẽ tiếp tục phục vụ cho đến hết nhiệm kỳ thứ ba.[34] Những tranh cãi về mối quan hệ giữa Brown và Blair tiếp tục kéo dài quá kỳ bầu cử năm 2005 khi Đảng Lao động vẫn duy trì thế đa số nhưng giảm số ghế trong quốc hội. Dù Brown và Blair hợp tác với nhau trong chiến dịch vận động nhưng xuất hiện trên các phương tiện truyền thông nước Anh những tin tức về mối bất hòa giữa hai người.

Bị áp lực từ bên trong đảng, ngày 7 tháng 9 năm 2006, Blair tuyên bố sẽ rút lui trong vòng một năm.[35] Như vậy, Brown là ứng cử viên sáng giá nhất cho chức vụ thủ tướng, nhất là khi trong mắt của các đảng viên, ông là một chính khách có tầm nhìn trong cung cách lãnh đạo và có khả năng thích ứng với những biến đổi toàn cầu.

Brown là thủ tướng đầu tiên đến từ một hạt bầu cử ở Scotland kể từ Sir Alec Douglas-Home năm 1964. Ông cũng là một trong bốn thủ tướng không theo học tại Đại học Oxford và Đại học Cambridge, ba người kia là Bá tước đảo Bute (Đại học Leiden), Lord John Russell (Đại học Edinburgh), và Neville Chamberlain (Đại học Khoa học Mason, về sau là Đại học Birmingham).[36] Trong khi đó, cũng có những thủ tướng chưa từng tốt nghiệp đại học như Công tước Wellington, Benjamin Disraeli, David Lloyd George, Winston Churchill, James Callaghan, và John Major.

Từ tháng 1 năm 2007, báo chí tường thuật rằng Brown "không còn giữ kẽ về ý định muốn dời về ngôi nhà số 10 trong thời gian tới" - mặc dù rõ ràng ông và gia đình thích sống trong ngôi nhà rộng rãi hơn ở số 11 đường Downing (dành cho Bộ trưởng Tài chính).[37] Trong tháng 1 năm 2007, khi nói chuyện ở Hội Fabian về chủ đề "Thập niên kế tiếp" Brown nhấn mạnh đến các vấn đề như giáo dục, phát triển quốc tế, thu hẹp khoảng cách giàu nghèo ("bình đẳng trong cơ hội và minh bạch trong lợi tức"), chấn hưng tinh thần dân tộc, phục hồi lòng tin trong chính trường, và tìm kiếm sự ủng hộ của người dân cho cuộc chiến chống khủng bố như là những ưu tiên hàng đầu của ông.[38]